DP L

対戦ゲームの読み切り問題

盤面を定義域とするDP

盤面は範囲で表現できる

先手後手を区別する必要はない

先手も後手も「自分の得点-相手の得点」を最大化する

メモ化してない素朴な再帰

サンプルコードは全部成功する

code:python

def solve(N, XS):

def first(L, R):

# debug(": L, R", L, R)

if L == R:

return max(

)

return first(0, N - 1)

このままではTLEなのでCythonでコンパイルする

「計算が済んでないことを確認するために取りえない値を入れておく」が、正負両方取りうるので計算済みかどうかを持つ配列も作った

十分大きい値にしておく手もあったな

boolを使うとエラーなのでintにしといた

code:cython

cdef first(L, R):

if L == R:

pos = L * N + R

else:

right = first(L + 1, R)

else:

left = first(L, R - 1)

if x > ret:

ret = x

return ret

cdef solve():

for i in range(N * N):

return first(0, N - 1)

def main():

global N, XS

# parse input

N = int(input())

XS = list(map(int, input().split()))

print(solve())